f(x) g(x)
x = 10^(-14): 0.4884981308350689 0.4999999999999988
x = 10^(-15): 0.44408920985006256 0.4999999999999999
x = 10^(-16): 0.0 0.526 Midterm
NAME:
Time Allowed: 1 hour 30 mins
Answer SECTION A and TWO of the three optional sections (B, C, D). If you have answered more than than the required two optional sections, you will be given credit for your best two optional sections. As a guide, I suggest you spend around 30 minutes on each section.
Please indicate your answers to multiple choice questions clearly with an ╳ to the left of your answers. Answer the optional sections on separate paper.
Please label any additional paper you use with your name and page number.
Electronic devices are not needed and not permitted in this examination. You may use your own notes, limited to 2 sides of letter sized paper. Answer the questions to Section A in the boxes provided. Additional paper may be requested.
27 A: [40 points] Compulsory Section
- [2 points] Suppose that a quantity x \not= 0 is approximated by \widetilde{x}. What is the relative error in this approximation?
- [3 points] Let x_n = \frac{1 + n^2}{ 2 n^3 } \cos n.
For which of the following sequences (\varepsilon_n) do we have x_n = O(\varepsilon_n) as n\to\infty?
Please select all that apply.
\varepsilon_n = n^{-2}
\varepsilon_n = n^{-1}
\varepsilon_n = 1
\varepsilon_n = n
Section A continued.
- [3 points] How many floating point numbers are there in the interval [1,2) with binary precision k = 3?
- [3 points] What is the relative condition number of the function f(x) = x - 1?
- [3 points] What scaling would you use in a graph to verify algebraic decay (i.e. O(n^{-\alpha}) for some \alpha > 0)?
Linear scale
Semi-logarithmic with the x-axis scaled
Semi-logarithmic with the y-axis scaled
Log-log plot (logarithmic scaling in both x- and y-axes)
- [3 points] Let us define
\begin{align*} f(x) = \frac{\sqrt{1+x}-1}{x}, \qquad g(x) = \frac{1}{\sqrt{1+x} + 1}. \end{align*}
One may verify that f and g are mathematically identical (but you don’t have to). The following table is the output of evaluating f and g on \{10^{-14}, 10^{-15}, 10^{-16}\} in double precision floating point. Why are the function values different?
Section A continued.
- [4 points] Let f : [ 0, \tfrac\pi2 ] \to \mathbb R be given by f(x) = x^2\sin x - 1.
Show that there is a \xi \in [0,\tfrac\pi2] for which f(\xi) = 0.
- [2 points] Here, we apply Newton’s method to f from Question 7.
Newton iteration on f(x) = x^2 sin(x) - 1 with x1 = π/2 ┌───────────┬──────────┬────────────────┬─────────────────────┐ │ iteration │ sequence │ residual │ approximate α │ │ n │ x[n] │ r[n]=|f(x[n])| │ log r[n]/log r[n-1] │ ├───────────┼──────────┼────────────────┼─────────────────────┤ │ 1.0 │ 1.5708 │ 1.4674 │ NaN │ │ 2.0 │ 1.10371 │ 0.0876848 │ -6.34694 │ │ 3.0 │ 1.06891 │ 0.00165227 │ 2.63171 │ │ 4.0 │ 1.06822 │ 6.52732e-7 │ 2.22338 │ │ 5.0 │ 1.06822 │ 1.01918e-13 │ 2.10043 │ └───────────┴──────────┴────────────────┴─────────────────────┘
Why do we use the residuals r_n := |f(x_n)| instead of the errors |x_n - \xi| when we are approximating the order of convergence (\alpha) in this method?
- [4 points] Let g(x) := 1 + \frac{1}{x} and define x_1 = 1 and x_{n+1} = g(x_n). Suppose that (x_n) \to \xi.
What is the value of \xi?
Section A continued.
- [4 points] Write down the Lagrange form of the polynomial of degree at most n interpolating f on X = \{ x_0, \dots, x_n \}.
- [4 points] Consider the following finite difference table
\begin{align} x_0: \quad & f[x_0] = 0, \quad & f[x_0, x_1] = 1, \nonumber\\ x_1: \quad & f[x_1] = 0, \nonumber \end{align}
Which of the following statements are true?
Please select all that apply.
The table does not correspond to any function f,
The table determines a polynomial interpolant p of degreee at least 2,
We must have f'(x_1) = 1,
We must have x_0 = x_1,
- [5 points] Write down the Trapezoid rule on [-1,1] and show that it is exact for all polynomials of degree at most 1.
Choose TWO sections from B, C, D (each worth 30 points)
27.1 B: Midpoint Rule
Suppose f is twice continuously differentiable. We will consider the following midpoint quadrature rule given by
\begin{align*} \int_a^b f(x) \approx (b-a) f\big( \tfrac{a+b}2 \big). \end{align*}
That is, there is only one node x_0 = \tfrac{a+b}{2} with corresponding weight w_0 = b-a.
- [3 points] Show that this midpoint rule is exact for all polynomials of degree at most 1,
- [3 points] Write down the polynomial p_1 of degree at most 1 with p_1\big( \tfrac{a+b}{2} \big) = f\big( \tfrac{a+b}{2} \big) and p_1'\big( \tfrac{a+b}{2} \big) = f'\big( \tfrac{a+b}{2} \big),
- [3 points] Expand f about \tfrac{a+b}2 to show that there exists \xi_x \in [a,b] such that
\begin{align*} f(x) - p_1(x) = \frac{f''(\xi_x)}{2} \big(x - \tfrac{a+b}2\big)^2. \end{align*}
- [8 points] Show that
\begin{align*} \left| \int_{a}^b f(x) \mathrm{d}x - (b-a) f\big( \tfrac{a+b}{2} \big) \right| \leq \frac{\| f'' \|_{L^\infty([a,b])}}{24} (b-a)^3 . \end{align*}
Let z_{j} := a + j \frac{b-a}{n} for j = 0,\dots,n and note that \int_a^b f = \sum_{j=0}^{n-1} \int_{z_{j}}^{z_{j+1}} f.
- [5 points] Apply the midpoint rule on each interval [z_j, z_{j+1}] to write down a formula for the corrresponding composite rule on [a,b]. Give the weights \{w_j\} and nodes \{x_j\} of this rule.
- [4 points] Use the error estimate from Question 3 obtain an error estimate for the composite rule.
- [4 points] Suppose that a = -1, b = 1. Show that the midpoint rule is exact when f is continuous and odd.
27.2 C: Simple Iteration
Define g(x) = 1 + \frac{1}{1 + x} and I := [1,2].
- [3 points] Show that g(x) \in I for all x \in I.
- [3 points] Which theorem guarantees the existence of a fixed point \xi = g(\xi) \in I.
- [3 points] Compute the value of \xi.
- [3 points] Show that L := \max_{x \in I} |g'(x)| = \frac14.
- [3 points] Explain why this means the iteration x_{n+1} = g(x_n) converges to \xi for all x_1 \in I.
- [5 points] What is the order of convergence?
- [5 points] What is the asymptotic error constant?
- [5 points] Fix x_1 \in I. Find n for which the error bound |x_{n+1} - \xi| \leq \frac{1}{64} is guaranteed.
Choose TWO sections from B, C, D (each worth 30 points)
27.3 D: Newton’s Method for Repeated Roots
- [2 points] Show that f(x) = e^x - x - 1 satisfies f(0) = f'(0) = 0 and f''(0) \not= 0.
- [2 points] Here, we apply Newton’s method to f(x) = e^x - x - 1. What is the order of convergence?
┌───────────┬─────────────┬───────────────┬─────────────────────┐
│ iteration │ sequence │ error │ approximate α │
│ n │ x[n] │ e[n]=|x[n]-ξ| │ log e[n]/log e[n-1] │
├───────────┼─────────────┼───────────────┼─────────────────────┤
│ 1.0 │ 3.1 │ 3.1 │ NaN │
│ 2.0 │ 2.24624 │ 2.24624 │ 0.71527 │
│ 3.0 │ 1.512 │ 1.512 │ 0.51088 │
│ 4.0 │ 0.939627 │ 0.939627 │ -0.150621 │
│ 5.0 │ 0.542328 │ 0.542328 │ 9.826 │
│ 6.0 │ 0.295555 │ 0.295555 │ 1.99205 │
│ 7.0 │ 0.155046 │ 0.155046 │ 1.52927 │
│ 8.0 │ 0.0795256 │ 0.0795256 │ 1.35817 │
... ... ... ...
│ 12.0 │ 0.0050958 │ 0.0050958 │ 1.15071 │
│ 13.0 │ 0.00255006 │ 0.00255006 │ 1.13113 │
│ 14.0 │ 0.00127557 │ 0.00127557 │ 1.116 │
│ 15.0 │ 0.000637923 │ 0.000637923 │ 1.10398 │
│ 16.0 │ 0.000318995 │ 0.000318995 │ 1.0942 │
│ 17.0 │ 0.000159506 │ 0.000159506 │ 1.0861 │
│ 18.0 │ 7.97552e-5 │ 7.97552e-5 │ 1.07927 │
│ 19.0 │ 3.98781e-5 │ 3.98781e-5 │ 1.07345 │
│ 20.0 │ 1.99392e-5 │ 1.99392e-5 │ 1.06843 │
│ 21.0 │ 9.96963e-6 │ 9.96963e-6 │ 1.06404 │
└───────────┴─────────────┴───────────────┴─────────────────────┘
Consider the modified Newton’s method
\begin{align*} x_{n+1} = x_n - 2 \frac{f(x_n)}{f'(x_n)}. \end{align*}
- [2 points] We apply this method to f(x) = e^x - x - 1. Compare the table to that of the standard Newton method.
┌───────────┬─────────────┬───────────────┬─────────────────────┐ │ iteration │ sequence │ error │ approximate α │ │ n │ x[n] │ e[n]=|x[n]-ξ| │ log e[n]/log e[n-1] │ ├───────────┼─────────────┼───────────────┼─────────────────────┤ │ 1.0 │ 3.1 │ 3.1 │ NaN │ │ 2.0 │ 1.39248 │ 1.39248 │ 0.292634 │ │ 3.0 │ 0.313183 │ 0.313183 │ -3.50653 │ │ 4.0 │ 0.0163206 │ 0.0163206 │ 3.54474 │ │ 5.0 │ 4.43937e-5 │ 4.43937e-5 │ 2.43539 │ │ 6.0 │ 3.27151e-10 │ 3.27151e-10 │ 2.17918 │ └───────────┴─────────────┴───────────────┴─────────────────────┘
Now suppose that f:[a,b]\to\mathbb R is four times continuously differentiable with root \xi \in (a,b) of multiplicity 2: that is, f(\xi) = f'(\xi) = 0 and f''(\xi) \not= 0. Further, we suppose that there exists A > 0 such that
\begin{align*} \left| \frac{f'''(x) + f^{(4)}(x) (x - \xi)}{f''(y)} \right| \leq A \end{align*}
for all x,y \in [a,b]. The aim of this section is to show that the modified Newton method converges at least quadratically to \xi for all x_1 \in [a,b] with |x_1 - \xi| \leq A^{-1}.
Notice that the modified Newton method can be written
\begin{align*} x_{n+1} - \xi &= \frac{ f'(x_n)(x_n - \xi) - 2 f(x_n) }{ f'(x_n) }. \end{align*}
- [8 points] By expanding the numerator g(x) := f'(x) (x - \xi) - 2 f(x) and denominator h(x) := f'(x), show that there exist \eta_n, \theta_n between x_n and \xi such that
\begin{align*} x_{n+1} - \xi &= \frac {\frac1{3!} g'''(\eta_n) (x_n - \xi)^3} {h'(\theta_n) (x_n - \xi) } % = \frac16 \left[ \frac {f'''(\eta_n) + f^{(4)}(\eta_n) (\eta_n - \xi) } {f''(\theta_n)} \right] (x_n - \xi)^2. \end{align*}
- [4 points] Hence show that, if |x_1 - \xi| \leq A^{-1}, then |x_{n+1} - \xi| \leq 6^{-n} |x_1 - \xi| and thus the modified Newton’s method converges.
- [4 points] Show that (x_n) converges at least quadratically to \xi.
- [4 points] What is the theoretical value of the asymptotic error constant when the modified Newton method is applied to f(x) = e^x - x - 1?
- [4 points] Show that the modified Newton method converges in 1 iteration for functions of the form f(x) = (x - \xi)^2.
END